//
// Created by Administrator on 2021/4/9.
//

/*
给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

#include <iostream>
#include <climits>
#include <queue>

using namespace std;

//definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:

    int minDepth(TreeNode *root) {
        /** 找到一棵树的最小深度
         * 对某个节点，最小深度 = min(左子树最小深度，右子树最小深度) + 1
         * 对于根节点，如果有一侧没有子数，则得从另一侧计算**/
        if (root == nullptr) return 0;
        if (root->left == nullptr and root->right == nullptr) return 1;
        else if (root->left == nullptr) return minDepth(root->right) + 1;
        else if (root->right == nullptr) return minDepth(root->left) + 1;
        else
            return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

class Solution2 { // 题解 dfs
public:
    int minDepth(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }
        if (root->left == nullptr && root->right == nullptr) {
            return 1;
        }
        int min_depth = INT_MAX;
        if (root->left != nullptr) {
            min_depth = min(minDepth(root->left), min_depth);
        }
        if (root->right != nullptr) {
            min_depth = min(minDepth(root->right), min_depth);
        }
        return min_depth + 1;
    }
};

class Solution3 { // 题解 bfs
public:
    int minDepth(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }
        queue<pair<TreeNode *, int> > Q;
        Q.emplace(root, 1);
        while (!Q.empty()) {
            TreeNode *node = Q.front().first;
            int depth = Q.front().second;
            Q.pop();
            if (node->left == nullptr && node->right == nullptr) {
                return depth; // 某一层出现叶子节点，返回结果
            }
            if (node->left != nullptr) {
                Q.emplace(node->left, depth + 1);
            }
            if (node->right != nullptr) {
                Q.emplace(node->right, depth + 1);
            }
        }

        return 0;
    }
};

int main() {
    auto t5 = TreeNode(7);
    auto t4 = TreeNode(15);
    auto t3 = TreeNode(20, &t4, &t5);
    auto t2 = TreeNode(9);
    auto t1 = TreeNode(3, &t2, &t3);


    auto n5 = TreeNode(6);
    auto n4 = TreeNode(5, nullptr, &n5);
    auto n3 = TreeNode(4, nullptr, &n4);
    auto n2 = TreeNode(3, nullptr, &n3);
    auto n1 = TreeNode(2, nullptr, &n2);

    Solution sol;
    cout << sol.minDepth(&t1) << endl;
    cout << sol.minDepth(&n1) << endl;
    return 0;
}